package com.wkr.leetcode;

import java.util.*;

public class Main {

    public static void main(String[] args) {

        ListNode l1 = generateListNode("1->2->3->null");
        ListNode l2 = generateListNode("1->2->3->null");
        System.out.println(addTwoNumbers(l1, l2));


        System.out.println(partition(generateListNode("1->4->3->2->5->2"), 3));
        System.out.println("++++++++++++++++++++++++++++++");
        System.out.println(removeNthFromEnd(generateListNode("1->4->3->2->5->2"), 2));

        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = a;
        getRingHeadAndTail(a);
        System.out.println(deleteDuplicates(generateListNode("1->1->2->3->3")));
        System.out.println(deleteDuplicates(generateListNode("1->2->3->3->3->3->4->4->5")));
    }


    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * 给你这个链表：1->2->3->4->5
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     * 主体思路：剪切链表，将剪切后的链表做反转，再凭借剩下的链表再周而复始进行
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode prev = new ListNode(-1, head);
        ListNode res = prev;
        int count = 0;
        ListNode copy = head;
        while (Objects.nonNull(head)) {
            count++;
            if (count == k) {
                // after = 3->4->5->null
                ListNode after = head.next;
                // head = 2->null
                head.next = null;
                // temp = 1->2->null
                ListNode temp = copy;
                // [2->1->null, 1->null]
                ListNode[] headAndTail = reverse(temp);
                // prev->2->1->null
                prev.next = headAndTail[0];
                // 1->3->4->5->null
                headAndTail[1].next = after;
                // prev = 1->3...
                prev = headAndTail[1];
                // head = 1->3...
                head = headAndTail[1];
                // copy = 3->...
                copy = after;
                count = 0;
            }
            // head = 3
            head = head.next;
        }
        return res.next;
    }

    /**
     * 反转链表并获取首末节点
     */
    public static ListNode[] reverse(ListNode head) {
        ListNode[] headAndTail = new ListNode[2];
        headAndTail[1] = head;
        ListNode prev = new ListNode(-1, null);
        while (Objects.nonNull(head)) {
            ListNode temp = head.next;
            head.next = prev.next;
            prev.next = head;
            head = temp;
        }
        headAndTail[0] = prev.next;
        return headAndTail;
    }


    /**
     * 移除未排序链表中的重复节点。保留最开始出现的节点
     * 1-2-2-2-3
     */
    public static ListNode removeDuplicateNodes(ListNode head) {
        Set val = new HashSet();
        ListNode node = head;
        ListNode last = head;
        while (Objects.nonNull(head)) {
            if (!val.add(head.val)) {
                // 存在重复节点
                // 当前head = b:1
                // 如 a:1->b:1->2
                // head = 2
                head = head.next;
                // last = a:1
                // a:1 -> 2
                last.next = head;
            } else {
                // 不存在重复节点
                // 记录当前节点
                last = head;
                head = head.next;
            }
        }
        return node;
    }

    /**
     * 移除未排序链表中的重复节点,解法2
     */
    public static ListNode removeDuplicateNodes2(ListNode head) {
        Set<Integer> val = new HashSet<>();
        ListNode node = new ListNode(-1, head);
        ListNode res = node;
        while (Objects.nonNull(node.next)) {
            if (!val.add(node.next.val)) {
                node.next = node.next.next;
                continue;
            }
            node = node.next;
        }
        return res.next;
    }

    /**
     * 获取环的长度
     */
    public static int loopLength(ListNode head) {
        ListNode tmp1 = head;
        ListNode tmp2 = head;
        int length = 0;
        int metCount = 0;
        while (tmp2.next != null && tmp2.next.next != null) {
            tmp1 = tmp1.next;
            tmp2 = tmp2.next.next;

            if (tmp1.equals(tmp2)) {
                metCount++;
            }
            if (!tmp1.equals(tmp2) && metCount == 1) {
                length++;
            }
            if (metCount == 2) {
                return length + 1;
            }

        }
        return length;
    }

    /**
     * 检测链表是否有环
     */
    public static boolean checkLoop(ListNode head) {
        ListNode tmp1 = head;
        ListNode tmp2 = head;
        while (tmp2 != null && tmp2.next != null && tmp2.next.next != null) {
            tmp1 = tmp1.next;
            tmp2 = tmp2.next.next;
            if (tmp1.equals(tmp2)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 反转链表
     */
    public static ListNode reverseListNode(ListNode head) {
        ListNode node = new ListNode(0, null);
        while (head != null) {
            // temp = 2->3->4
            ListNode temp = head.next;
            // 1->null
            head.next = node.next;
            // node->1
            node.next = head;
            // head = 2->3->4
            head = temp;
        }
        return node.next;
    }

    /**
     * 成对反转链表
     */
    public static ListNode twinReverseListNode(ListNode head) {
        ListNode node = new ListNode(0, head);
        ListNode res = node;
        while (node.next != null && node.next.next != null) {
            // one = 1->2->3->4
            ListNode one = node.next;
            // two = 2->3->4
            ListNode two = node.next.next;
            // node->2->3->4
            node.next = two;
            // 1->3->4
            one.next = two.next;
            // 2->1->3->4
            two.next = one;
            // node = 1->3->4
            node = one;
        }
        return res.next;
    }

    /**
     * 返回倒数第K个节点
     */
    public static ListNode kRes(ListNode head, int k) {
        ListNode temp = head;
        int i = 0;
        while (head != null) {
            i++;
            head = head.next;
            if (i > k) {
                temp = temp.next;
            }
        }
        return temp;
    }

    /**
     * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
     * 输入: 1->2->3->4->5->NULL, k = 2
     * 输出: 4->5->1->2->3->NULL
     * 解释:
     * 向右旋转 1 步: 5->1->2->3->4->NULL
     * 向右旋转 2 步: 4->5->1->2->3->NULL
     */
    public static ListNode rotateRight(ListNode head, int k) {
        int i = 0;
        ListNode temp = head;
        if (head == null || head.next == null) {
            return head;
        }
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        head = temp;
        k = k % length;
        while (i < k) {
            i++;
            // head = 3->4->null
            while (head.next.next != null) {
                head = head.next;
            }
            // tmp = 4->null
            ListNode tmp = head.next;
            // 3->null
            head.next = head.next.next;
            // 4->1->2->3->null
            tmp.next = temp;
            // head = 4->1->2->3->null
            head = tmp;
            // temp = 4->1->2->3->null
            temp = tmp;
        }
        return temp;
    }

    /**
     * 闭环思路
     */
    public static ListNode rotateRight2(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        // 存放循环链表
        ListNode temp = head;
        // 存放待返回的链表
        ListNode start = head;
        int length = 0;
        while (head.next.next != null) {
            length++;
            head = head.next;
        }
        length = length + 2;
        head.next.next = temp;
        k = k % length;
        int i = 0;
        while (i < length - k - 1) {
            i++;
            temp = temp.next;
            start = start.next;
        }
        start = start.next;
        temp.next = null;
        return start;
    }

    /**
     * 合并两升序链表
     */
    public static ListNode mergeSortedListNode(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1, null);
        ListNode prev = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                head.next = list2;
                list2 = list2.next;
            } else {
                head.next = list1;
                list1 = list1.next;
            }
            head = head.next;
        }
        if (list1 != null) {
            head.next = list1;
        }
        if (list2 != null) {
            head.next = list2;
        }

        return prev.next;
    }


    /**
     * 生成链表
     * @param nodeStr 1->2->3->null
     */
    public static ListNode generateListNode(String nodeStr) {
        String[] nodes = nodeStr.split("->");
        ListNode temp = new ListNode(-1);
        ListNode prev = temp;
        for (String node : nodes) {
            if ("null".equals(node)) {
                temp.next = null;
            } else {
                temp.next = new ListNode(Integer.valueOf(node));
            }
            temp = temp.next;
        }
        return prev.next;
    }
    /**
     * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
     * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> one = new Stack<>();
        Stack<Integer> two = new Stack<>();
        while (Objects.nonNull(l1)) {
            one.push(l1.val);
            l1 = l1.next;
        }
        while (Objects.nonNull(l2)) {
            two.push(l2.val);
            l2 = l2.next;
        }
        boolean carry = false;
        Stack<Integer> res = new Stack<>();
        int count = Math.min(one.size(), two.size());
        for (int i = 0; i < count; i++) {
            int sum = one.pop() + two.pop();
            if (carry) {
                sum++;
                carry = false;
            }
            if (sum > 9) {
                carry = true;
            }
            sum = sum % 10;
            res.push(sum);
        }
        while (one.size() > 0) {
            int sum = one.pop();
            if (carry) {
                sum++;
                carry = false;
            }
            if (sum > 9) {
                carry = true;
            }
            sum = sum % 10;
            res.push(sum);
        }
        while (two.size() > 0) {
            int sum = two.pop();
            if (carry) {
                sum++;
                carry = false;
            }
            if (sum > 9) {
                carry = true;
            }
            sum = sum % 10;
            res.push(sum);
        }
        if (carry) {
            res.push(1);
        }
        ListNode temp = new ListNode(-1);
        ListNode node = temp;
        while (res.size() > 0) {
            temp.next = new ListNode(res.pop());
            temp = temp.next;
        }
        return node.next;
    }

    /**
     * 给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
     * 你应当保留两个分区中每个节点的初始相对位置。
     *
     * 输入：head = 1->4->3->2->5->2, x = 3
     * 输出：1->2->2->4->3->5
     */
    public static ListNode partition(ListNode head, int x) {

        ListNode littleNode = new ListNode(-1, null);
        ListNode littleNodeTemp = littleNode;
        ListNode bigNode = new ListNode(-1, null);
        ListNode bigNodeTemp = bigNode;
        while (Objects.nonNull(head)) {
            ListNode temp = head.next;
            if (head.val < x) {
                head.next = littleNode.next;
                littleNode.next = head;
                littleNode = littleNode.next;
            } else {
                head.next = bigNode.next;
                bigNode.next = head;
                bigNode = bigNode.next;
            }
            head = temp;
        }
        littleNode.next = bigNodeTemp.next;
        return littleNodeTemp.next;
    }

    /**
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 1->4->3->2->5->2
     */
    private static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode head2 = new ListNode(-1, head);
        ListNode prev = head2;
        ListNode temp = head2;
        int i = 0;
        while (Objects.nonNull(head2.next)) {
            i++;
            if (i > n) {
                temp = temp.next;
            }
            head2 = head2.next;
        }
        temp.next = temp.next.next;
        return prev.next;
    }

    /**
     * 获取环的首尾节点
     */
    private static ListNode[] getRingHeadAndTail(ListNode node) {
        ListNode[] res = new ListNode[2];
        Set<ListNode> set = new HashSet<>();
        ListNode tail = null;
        while (node != null) {
            if (!set.add(node)) {
                res[0] = node;
                res[1] = tail;
                break;
            }
            tail = node;
            node = node.next;
        }
        return res;
    }

    /**
     * 删除重复节点2
     * 输入：1->2->3->3->3->4->4->5
     * 输出: 1->2->5
     * 112
     */
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode temp = new ListNode(-1, head);
        // 返回的节点
        ListNode prev = temp;
        // 存储重复的值
        Set<Integer> re = new HashSet<>();
        while (temp.next != null && temp.next.next != null) {
            // 1 2
            if (temp.next.val == temp.next.next.val) {
                re.add(temp.next.val);
                temp.next = temp.next.next.next;
            } else {
                // 1->1->1->2 在1->2时候，判断1还能加入到集合么，不能的话跳过当前
                if (!re.add(temp.next.val)) {
                    temp.next = temp.next.next;
                    continue;
                }
                temp = temp.next;
            }
        }
        // 1->1->1 解决最后重复是奇数个的情况
        if (temp.next != null && !re.add(temp.next.val)) {
            temp.next = temp.next.next;
        }
        return prev.next;
    }
}
